11726

Created at : 2023-10-18 15:39
11726

#include <iostream>

using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

uint32_t n;
uint64_t *p;

cin >> n;

p = new uint64_t[max(n+1, uint32_t(3))];

p[0] = 0;
p[1] = 1;
p[2] = 2;
for(uint32_t i = 3; i < n+1; ++i)
{
	p[i] = (p[i - 1] + p[i - 2]) % 10007;
}

cout << p[n]; 

return 0;
}

전형적인 피보나치수열 문제.
P[n] = P[i-1] + P[i-2]
가 되는 이유는 P[i-1]의 우측에 타일 하나를 두고, P[i-2]의 우측에 가로로 만든 타일 2개를 두는 방식으로 하면 P[n]을 구할 수 있다.